JZ4 重建二叉树

JZ4 重建二叉树

链接：https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6

题目

给定某二叉树的前序遍历和中序遍历，请重建出该二叉树并返回它的头结点。 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

提示: 1.0 <= pre.length <= 2000 2.vin.length == pre.length 3.-10000 <= pre[i], vin[i] <= 10000 4.pre 和 vin 均无重复元素 5.vin出现的元素均出现在 pre里 6.只需要返回根结点，系统会自动输出整颗树做答案对比

解答一

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length ==0) return null;

        return dfs(pre, in, 0, pre.length - 1, 0, in.length - 1);
    }
    
    /**
     * 解题思路，后续遍历的最后一个元素就是根节点
     * 这个 head1 和 tail1 前序数组的下标
     * 这个 head2 和 tail2 中序数组的下标
     */
    private TreeNode dfs(int[] pre, int[] in, 
                         int head1, int tail1, 
                         int head2, int tail2) {
        // 健壮性判断，当中序的头下标大于尾下标时返回 null
        if(tail2 < head2) return null;
        
        int val = pre[head1];
        TreeNode root = new TreeNode(val);
        
        // 如果当前头尾下标相等了，表示遍历完成了
        // 这里也可以是 tail1 == head1
        if(tail2 == head2) return root;
        
        int mid = 0; // 中间下标
        // 根据前序的 root 找到 中序 root 的位置
        while(in[mid + head2] != val) 
            mid++;
        
        // 示例：
        // 第一次：
        // 前：1,2,3,4,5,6,7 这里通过 mid 切成 234-567
        // 中：3,2,4,1,6,5,7 这里 mid 是 3 切成 324-657
        // 第二次右边：
        // 前：567 这里通过 mid 即 1 + 4（head1） 切成 6-7
        // 中：657 这里 mid 是 1 + 4（head2） 切成 6-7
        
        root.left =  dfs(pre, in,
                         // 左半部分的前序数组下标
                         // 去掉第一个中点，然后它也是从 mid 对半切的
                         head1 + 1,head1 + mid, 
                         // 左半部分的中序数组下标
                         head2,  head2 + mid - 1);
        
        root.right =  dfs(pre, in, 
                          head1 + mid + 1, tail1, 
                          head2 + mid + 1, tail2);
        
        return root;
    }
}

23-5-23

耗时： 10min

这里注意先序要去掉第一个 root，即下面 pre[1:idx+1] 这块

func reConstructBinaryTree(pre []int, vin []int) *TreeNode {
    if len(pre) == 0 {
        return nil
    }

    root, idx := pre[0], 0
    for i := 0; i < len(vin); i++ {
        if root == vin[i] {
            idx = i
            break
        }
    }

    return &TreeNode{
        Val:   root,
        Left:  reConstructBinaryTree(pre[1:idx+1], vin[:idx]),
        Right: reConstructBinaryTree(pre[idx+1:], vin[idx+1:]),
    }
}